B-trees are hierarchical structures used to store sorted data for efficient access. In a typical B-tree structure, the shape of a B-tree depends on a modification history of the B-tree. For this reason, two B-trees with the same data may not have the same internal nodes, and as such, may vary in their representations. A collection of computing devices may store B-trees with the same content in each of the computing devices within the collection. Due to varied representations, synchronized modification of B-trees amongst a collection of computing devices may require sending a replication of an entire database every time a modification is made, implementation of state based modifications, implementation of layer based modifications, locking a segment of a database resulting in unavailability of portions of data, etc.
Generating reproducible B-tree structures presents challenges due to complexities and inefficiencies involved. One example of generating a reproducible structure is using a virtual treap data structure, which is a randomized balanced binary search tree using heap property, and partitioning the virtual treap data structure into a B-tree. However, the treap structure requires complex data manipulations. Another example is using a probabilistic B-tree, where the number of values in each node is determined probabilistically based on the data in the tree, however, a rolling hash of all of the data values need to be calculated, resulting into inefficiency and lack of flexibility in smaller data exchanges among multiple devices. Additionally, skip lists, which are data structures with stacked linked lists, may be deterministic, but changing an individual data element may require changing potentially all values in the list.